import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 双子数
 * User: DELL
 * Date: 2024-05-23
 * Time: 10:36
 */
public class Main2 {
    static boolean[] primes = new boolean[5000001];
    static ArrayList<Integer> primesList = new ArrayList<>();
    static long MAX = 23333333333333L;
    static long MIN = 2333L;

    public static void main(String[] args) {
        init();
        long ans = 0;
        for (int i = 0; i < primesList.size(); i++) {
            for (int j = i + 1; j < primesList.size(); j++) {
                long temp1 = primesList.get(i);
                long temp2 = primesList.get(j);
                long temp = temp1 * temp1 * temp2 * temp2;
                if (temp <= MAX && temp >= MIN) {
                    ans++;
                } else if (temp > MAX) {
                    break;
                }
            }
        }
        System.out.println(ans);
    }

    /**
     * 缓存素数
     */
    private static void init() {
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;
        for (int i = 2; i < 5000001; i++) {
            if (primes[i]) {
                primesList.add(i);
                for (int j = i; (long) i * j < 5000001; j++) {
                    primes[i * j] = false;
                }
            }
        }
    }
}
